package com.practice.zuocy.base.class02;

/**
 * 递归基础（引出Master公式）：
 * 【题目】：求数组arr[L...R]中的最大值，怎么用递归方法实现。
 * 【解法】：
 * （1）将[L...R]范围强行的分成左右两半。左边：[L...Mid]；右边：[Mid+1...R]
 * （2）左边部分求最大值，右边部分求最大值
 * （3）[L...R]范围上的最大值，是max{左部分最大值, 右部分最大值}、
 * 【注意】：步骤（2）是一个递归过程，当范围上只有一个数，就可以不再递归了（递归结束条件）。
 */
public class Code08_GetMax {

	// 求arr中的最大值
	public static int getMax(int[] arr) {
		return process(arr, 0, arr.length - 1);
	}

	// arr[L..R]范围上求最大值  L ... R   N
	public static int process(int[] arr, int L, int R) {
		if (L == R) { // arr[L..R]范围上只有一个数，直接返回，base case
			return arr[L];
		}
		int mid = L + ((R - L) >> 1); // 中点   	1
		int leftMax = process(arr, L, mid);
		int rightMax = process(arr, mid + 1, R);
		return Math.max(leftMax, rightMax);
	}

}
